#include "collagewindow.h"
#include <QFileDialog>
#include <QFile>
#include <QMessageBox>
#include <QPainter>
#include <QFile>
#include <QFileDialog>
#include <QObject>
#include <QList>
#include <QImage>
#include <QTime>
#include <QDebug>
#include <QLineF>
#include <QApplication>
#include <QDesktopWidget>

/**
 * Constructeur
 */
CollageWindow::CollageWindow()
{
    // On etablie les format accepté lors de l'ajout de photo
    supportedFormatList.insert(0,"png");
    supportedFormatList.insert(0,"jpg");
    supportedFormatList.insert(0,"JPG");
    supportedFormatList.insert(0,"bmp");

    this->params = new Parametre();

    this->polygon = new QPolygon();

    //initialisation du générateur de nombre aléatoire
    qsrand(QTime::currentTime().msec());
}

/**
 * Destructeur
 */
CollageWindow::~CollageWindow()
{
    delete polygon;
    delete params;
}

/**
 *  Retourne un pixmap 350*350 dessinant un polygone donné
 */
QPixmap* CollageWindow::GetPolygonePixmap(QPolygon* pol, int width, int height)
{
    //On dessine une pixmap de la taille spécifiée
    QPixmap* pix = new QPixmap(QSize(width,height));

    //Initialisation du pixmap
    pix->fill();

    //On dessine le polygone
    QPainter p(pix);
    QPen pen(Qt::black, 5);
    p.setPen(pen);
    p.drawPolygon(*pol);

    return pix;
}

/**
 * dessine un cercle comme polygone
 */
void CollageWindow::SetCercle()
{
    int nbseg=20;
    double Pas = 2*M_PI/nbseg;
    double angle;
    double radius=130;

    QPoint o(170,170);
    QVector<QPoint> v;

    for(int i = 0; i<nbseg; i++)
    {
        angle = i*Pas;

        QPoint p( o.x() + radius*cos( angle ), o.y() + radius*sin( angle ) );
        v.insert(0,p);
    };

    polygon = new QPolygon(v);
}

/**
 * dessine un rectangle comme polygone
 */
void CollageWindow::SetRectangle()
{
    QVector<QPoint> v;
    v.insert(0,QPoint(50,100));
    v.insert(0,QPoint(300,100));
    v.insert(0,QPoint(300,250));
    v.insert(0,QPoint(50,250));

    polygon = new QPolygon(v);
}

void CollageWindow::showMessage(QString s)
{

}

/**
 * Supprime les photos sélectionnés dans l'interface
 */
void CollageWindow::supprimePhoto()
{
    //pour chaque item sélectionné
    foreach (QListWidgetItem *item, listPhotos->selectedItems())
    {
        //on supprime l'image de la liste métier
        if(!this->params->removeImage(item->data(Qt::UserRole).toString()))
        {//Si l'image n'a pas put être supprimée
            showMessage("Erreur suppression de l'image.");
        }

        //on supprime l'item de l'interface
        delete item;
    }
    //maj du nbr de photos
    on_update_delete();
}

/**
 * Supprime toutes les photos
 */
void CollageWindow::supprimeLesPhotos()
{
    while(listPhotos->count()>0)
    {
        QListWidgetItem* item = listPhotos->item(0);
        //on supprime l'image de la liste métier
        if(!this->params->removeImage(item->data(Qt::UserRole).toString()))
        {//Si l'image n'a pas put être supprimée
            showMessage("Erreur suppression de l'image.");
        }

        //on supprime l'item de l'interface
        delete item;
    }

    //maj du nbr de photos
    on_update_delete();
}

/**
 * Spécifie si la suppression doit être activée sur l'interface
 */
void CollageWindow::on_update_delete()
{
    if(listPhotos->count()==0)
    {
        listPhotos->labelDrop->show();
    }
    else
    {
        listPhotos->labelDrop->hide();
    }
}

/**
 * Ajout d'une photo
 */
void CollageWindow::addPhoto(QString s,bool filePrefix)
{
    QString fullname;

    if(filePrefix)
        fullname=s.mid(8);
    else
        fullname=s;

    //on créer le fichier
    QFile f(fullname);
    //on créer un objet FileInfo pour avoir le basename
    QFileInfo info(f);

    if(info.isFile())
    {
        if(supportedFormatList.contains(info.suffix()))
        {
            //on crée l'image
            Image *newImg = new Image(fullname);

            //on l'ajoute dans la liste des images utilisées
            QString error = this->params->addImage(newImg);

            //On vérifie si une erreur s'est produite
            if(!error.isEmpty())
            {
                this->showMessage("Un erreur s'est produite pendant l'ajout de l'image : "+fullname);
            }
            //Si aucune erreur, on ajoute l'image a la liste graphique
            else
            {
                //on créer l'item avec une icon a partir du fullname , le texte a partire du basename
                QListWidgetItem *item = new QListWidgetItem(QIcon(fullname),info.fileName().mid(0,10)+"...", listPhotos);
                listPhotos->addItem(item);

                //on associe comme data la position de l'image dans la liste métier
                item->setData(Qt::UserRole, newImg->getFilepath());
            }
        }
    }
    else
    {
        QDir dir(fullname);
        dir.setFilter(QDir::Files|QDir::Dirs | QDir::NoDotAndDotDot);
        QFileInfoList lst = dir.entryInfoList();
        for(int i = 0; i < lst.size(); i++)
        {
            QString s = lst.at(i).absolutePath()+"/"+lst.at(i).fileName();
            addPhoto(s);
        }
    }
}

/**
 * Ajout d'une photo par la boite de dialogue
 */
void CollageWindow::ajoutPhotoParDialog(QWidget* parent)
{
    QStringList fileNames;
    QString fullName;
    QFileDialog dialog(parent);

    //configuration de la boite de dialogue
    dialog.setDirectory(QDir::homePath());
    dialog.setFileMode(QFileDialog::ExistingFiles);

    //on construit la regle decrivant les format accepté
    QString filter="Image Files (";
    foreach(QString format,supportedFormatList)
        filter+="*."+format+" ";
    filter+=")";
    dialog.setNameFilter(QObject::trUtf8(filter.toStdString().c_str()));

    //on met dans filenames la liste des fichiers sélectionnés
    if (dialog.exec())
        fileNames = dialog.selectedFiles();

    foreach(fullName,fileNames)
    {
       addPhoto(fullName);
    }

    on_update_delete();
}

///////////////////////////////
////////////COLLAGE////////////
///////////////////////////////
/**
 *return true si le rectangle est dans le polygone
*/
bool CollageWindow::RectInsidePolygoneForme(QRect rect, QPoint imagePos, int rotation)
{
    QMatrix     matrix;
    QPolygonF    poly;
    QPolygon    poly2;

    //on transforme le rectangle en polygone
    poly = QPolygon(rect, true);
    poly2 = QPolygon(rect, true);

    //Préparation de la matrice
    matrix.translate(imagePos.x(),imagePos.y());
    matrix.translate(rect.width()/2,rect.height()/2);
    matrix.rotate(rotation);
    matrix.translate(-rect.width()/2,-rect.height()/2);

    //on place le polygone à l'endroit où sera dessiné l'image
    poly = matrix.map(poly);
    poly2 = matrix.map(poly2);

    //on vérifie que tous ses points sont dans le polygone de la forme
    foreach(QPoint point, poly2)
    {
        if(!this->polygon->containsPoint(point, Qt::OddEvenFill))
            return false;
    }

    //on vérifie que toute l'image est dans le polygone
    for(int i = 0; i < this->polygon->count() - 1; i++)
    {
        QLineF lineForme = QLineF(this->polygon->at(i), this->polygon->at(i+1));
        for(int j = 0; j < poly.count() - 1; j++)
        {
            QLineF lineImage = QLineF(poly.at(j), poly.at(j+1));
            if(lineForme.intersect(lineImage, new QPointF()) == QLineF::BoundedIntersection)
            {
                return false;
            }
        }
    }

    //l'image est dans le polygone
    return true;
}

/**
 *colle l'image spécifiée aux coordonnées spécifiées
*/
void CollageWindow::collageImage(QList<zoneImage*> listZoneImage, QPixmap* pixmap)
{
    //Définition du painter
    QPainter painter(pixmap);

    //dessin du polygone
    painter.drawPolygon(*this->polygon);

    //pour chaque image dans la liste
    foreach(zoneImage *zone, listZoneImage)
    {
        //on place le painter à l'emplacement spécifié
        painter.translate(zone->posImage.x(),zone->posImage.y());
        painter.translate(zone->image->width()/2,zone->image->height()/2);
        painter.rotate(zone->rotation);
        painter.translate(-zone->image->width()/2,-zone->image->height()/2);

        //dessin de l'image
        painter.drawImage(0,0,*zone->image);

        //remise a 0 de la transformation du painter
        painter.resetTransform();

        //si l'user veut des bordures
        if(this->params->getSizeBordure() > 0)
        {
            QMatrix     matrix;
            QPolygon    poly;
            QBrush      brush;
            QPen        pen;
            int         width;

            //taille photo en pixel
            if(this->params->getFormatPictureSize() == Pixel)
                width = (params->getSizeBordure()*params->getPictureSize())/100;
            else
                width = (params->getSizeBordure()*convertCmToPixel(params->getPictureSize()))/100;

            brush = QBrush(params->getColorBordure());
            pen = QPen(brush, width);
            painter.setPen(pen);

            //on transforme le rectangle en polygone
            poly = QPolygon(zone->image->rect());

            //Préparation de la matrice
            matrix.translate(zone->posImage.x(),zone->posImage.y());
            matrix.translate(zone->image->width()/2,zone->image->height()/2);
            matrix.rotate(zone->rotation);
            matrix.translate(-zone->image->width()/2,-zone->image->height()/2);

            //on place le polygone à l'endroit où sera dessiné l'image
            poly = matrix.map(poly);

            //l'image est dans le polygone
            painter.drawPolygon(poly);
        }
    }
}

/**
 *remplit une liste de QImage qui sera utilisée telle quelle dans le collage
*/
QList<zoneImage*> CollageWindow::fillListZoneImage(int nbrImages, int pictureSize)
{
    int numPhoto = 0;
    int index;
    QList<zoneImage*> listZoneImage = QList<zoneImage*>();

    if(params->getAddAllPicture() && params->getAutoParam() != pictureQuantityId)
    {
        foreach(Image *image,  params->getListImage())
        {
            //création de la zone d'image suivante
            zoneImage *newZone = new zoneImage();

            //copie de l'image d'origine
            newZone->image = new QImage(*image);

            //on la resize
            resizePicture(newZone->image, pictureSize);

            //calcul de la rotation aléatoire entre 0 et 360
            newZone->rotation = (qrand() % (360 + 1));

            //initialisation de la position
            newZone->posImage = QPoint(-1,-1);

            //on ajoute la zone à la liste
            listZoneImage.append(newZone);
        }
    }
    else
    {
        while(numPhoto < nbrImages)
        {
            //on récupère l'index de la prochaine photo
            index = (qrand() % (params->getListImage().count()));

            //création de la zone d'image suivante
            zoneImage *newZone = new zoneImage();

            //on garde en mémoire l'image d'origine
            newZone->image = new QImage(*params->getListImage().at(index));

            //on la resize
            resizePicture(newZone->image, pictureSize);

            //calcul de la rotation aléatoire entre 0 et 360
            newZone->rotation = (qrand() % (360 + 1));

            //initialisation de la position
            newZone->posImage = QPoint(-1,-1);

            //on ajoute la zone à la liste
            listZoneImage.append(newZone);

            //incrémentation du flag
            numPhoto++;
        }
    }

    return listZoneImage;
}

/**
 *ajoute le nombre d'image spécifié à une liste de QImage qui sera utilisée telle quelle dans le collage
*/
void CollageWindow::addListZoneImage(QList<zoneImage *> *listZoneImage, int nbrImagesToAdd, int pictureSize)
{
    int numPhoto = 0;
    int index;

    while(numPhoto < nbrImagesToAdd)
    {
        //on récupère l'index de la prochaine photo
        index = (qrand() % (params->getListImage().count()));

        //création de la zone d'image suivante
        zoneImage *newZone = new zoneImage();

        //on garde en mémoire l'image d'origine
        newZone->image = new QImage(params->getListImage().at(index)->copy());

        //on la resize
        resizePicture(newZone->image, pictureSize);

        //calcul de la rotation aléatoire entre 0 et 360
        newZone->rotation = (qrand() % (360 + 1));

        //initialisation de la position
        newZone->posImage = QPoint(-1,-1);

        //on ajoute la zone à la liste
        listZoneImage->append(newZone);

        //incrémentation du flag
        numPhoto++;
    }
}

/**
 *retire le nombre d'image spécifié à une liste de QImage qui sera utilisée telle quelle dans le collage
*/
void CollageWindow::removeListZoneImage(QList<zoneImage*> *listZoneImage, int nbrImagesToRemove)
{
    int numPhoto = 0;

    while(numPhoto < nbrImagesToRemove)
    {
        //on retire le premier élément
        listZoneImage->removeFirst();

        //incrémentation du flag
        numPhoto++;
    }
}

/**
 *remet les positions d'une liste d'image a 0 de façon a pouvoir la réutiliser
*/
void CollageWindow::resetListZoneImage(QList<zoneImage*> listImages)
{
    //pour chaque image dans la liste spécifiée
    foreach(zoneImage* zone, listImages)
    {
        //on ré-initialise a 0 sa position
        zone->posImage = QPoint(-1,-1);
    }
}

/**
 *copie une liste d'image
*/
QList<zoneImage*> CollageWindow::copyListZoneImage(QList<zoneImage*> listImages)
{
    QList<zoneImage*> res = QList<zoneImage*>();

    //pour chaque image dans la liste spécifiée
    foreach(zoneImage* zone, listImages)
    {
        zoneImage* newZone = new zoneImage();

        newZone->image = zone->image;
        newZone->posImage = zone->posImage;
        newZone->rotation = zone->rotation;

        res.append(newZone);
    }
    return res;
}

/**
 *destruction d'une liste d'image
*/
void CollageWindow::destroyListZoneImage(QList<zoneImage*> listImages, bool deleteImage = false)
{
    if (listImages.count() == 0)
        return;

    //pour chaque image dans la liste spécifiée
    foreach(zoneImage* zone, listImages)
    {
        if(deleteImage)
            delete zone->image;
        delete zone;
    }

    listImages.clear();
}

/**
 *resize de l'image spécifiée
*/
void CollageWindow::resizePicture(QImage *image, int pictureSize)
{
    if(params->getFormatPictureSize() == Cm)
        return resizePictureCm(image, pictureSize);
    else
        return resizePicturePx(image, pictureSize);
}

/**
 *Resize les images en Px
*/
void CollageWindow::resizePicturePx(QImage *image, int pictureSize)
{
    int newPX = pictureSize;

    if(image->width()>image->height())
    {
        //transformation de l'image
        *image = image->scaledToWidth(newPX);
    }
    else
    {
        //transformation de l'image
        *image = image->scaledToHeight(newPX);
    }
}

/**
 *Resize les images en Cm
*/
void CollageWindow::resizePictureCm(QImage *image, int pictureSize)
{
    int oldCM;
    int newCM = pictureSize;
    int oldPX;
    int newPX;

    if(image->widthMM() > image->heightMM())
    {
        //produit en croix pour convertir les cm en pixels
        oldCM = image->widthMM()/10;
        oldPX = image->width();
        newPX = (newCM * oldPX) / oldCM;

        //transformation de l'image
        *image = image->scaledToWidth(newPX);
    }
    else
    {
        //produit en croix pour convertir les cm en pixels
        oldCM = image->heightMM()/10;
        oldPX = image->height();
        newPX = (newCM * oldPX) / oldCM;

        //transformation de l'image
        *image = image->scaledToHeight(newPX);
    }
}

/**
 *Centre le polygone dans la zone de dessin
 */
bool CollageWindow::replacePolygon(QSize resultSize)
{
    QRect rectDessin, rectPolygone, newRectPolygone;
    QPoint centerDessin, centerPolygon, newCenterPolygon;

    //rectangle englobant la surface de dessin
    rectDessin = QRect(0,0,resultSize.width(), resultSize.height());

    //rectangle englobant le polygone
    rectPolygone = this->polygon->boundingRect();

    centerDessin = QPoint(rectDessin.width()/2, rectDessin.height()/2);
    centerPolygon = QPoint(rectPolygone.x()+(rectPolygone.width()/2), rectPolygone.y()+(rectPolygone.height()/2));

    //calcul du nouveau centre
    newCenterPolygon = QPoint(0,0);
    if(centerPolygon.x() > centerDessin.x())
        newCenterPolygon.setX(-(centerPolygon.x() - centerDessin.x()));
    else
        newCenterPolygon.setX(centerDessin.x() - centerPolygon.x());

    if(centerPolygon.y() > centerDessin.y())
        newCenterPolygon.setY(-(centerPolygon.y() - centerDessin.y()));
    else
        newCenterPolygon.setY(centerDessin.y() - centerPolygon.y());

    //application de la transformation
    polygon->translate(newCenterPolygon.x(), newCenterPolygon.y());

    return false;
}

/**
 *Modifie la taille du polygone en le contenant dans la zone de dessin
 *Retourne un booléen indiquant si le polygone a été retouché
 */
bool CollageWindow::resizePolygon(QSize resultSize)
{
    QTransform  trans;
    QPolygon    save;
    QRect       rectDessin;
    bool        resized = false;

    //rectangle englobant la surface de dessin
    rectDessin = QRect(0,0,resultSize.width(), resultSize.height());

    //Si le polygone est plus grand que la zone de dessin
    if(!rectDessin.contains(this->polygon->boundingRect()))
    {
        trans=trans.scale(0.8,0.8);

        //tant que le polygone ne rentre pas dans le dessin, on le rétrecit
        while(!rectDessin.contains(this->polygon->boundingRect()))
        {
            *this->polygon = trans.map(*this->polygon);
            replacePolygon(resultSize);
            resized = true;
        }
    }
    else
    {
        trans=trans.scale(1.05,1.05);
        save = *this->polygon;

        //tant que le polygone rentre dans le dessin, on l'agrandit
        while(rectDessin.contains(save.boundingRect()))
        {
            save = trans.map(*this->polygon);
            if(rectDessin.contains(save.boundingRect()))
            {
                *this->polygon = save;
                resized = true;
            }
        }

    }
    return resized;
}

/**
 * Lance le placement des images
 */
QPixmap* CollageWindow::Collage()
{
    if(params->getAutoParam() == resultSizeId)
        return TailleResultAuto();
    else if(params->getAutoParam() == pictureSizeId)
        return pictureSizeAuto();
    else if(params->getAutoParam() == pictureQuantityId)
        return pictureQuantityAuto();
    else
        return pictureSpacingAuto();
}

/**
 * placement des images avec la quantitée d'image automatique
 */
QPixmap* CollageWindow::pictureQuantityAuto()
{
    QPixmap     *pixRes;
    QSize       sizeResult;
    int         pictureQuantity;
    int         debut, fin, mil;
    bool        trouve;

    //initialisation des paramètres de recherche
    debut = 1;
    fin = 1000;
    trouve = false;
    mil = (debut + fin) / 2;

    //taille de la feuille
    sizeResult = QSize(params->getResultWidth(),params->getResultHeight());

    //nombre de photos par défaut
    pictureQuantity = mil;

    //On modifie la taille du polygone de forme en conséquence
    replacePolygon(sizeResult);
    while(resizePolygon(sizeResult))
        replacePolygon(sizeResult);

    //remplissage de la liste des images
    QList<zoneImage*> listZoneImage = fillListZoneImage(1, this->params->getPictureSize());

    while(PlacementListZoneImage(listZoneImage, sizeResult, params->getPictureSize(), params->getPictureDistance()))
    {
          //On augmente le nombre d'images
          addListZoneImage(&listZoneImage, 1, this->params->getPictureSize());
    }

    //on supprime la dernière image qui n'a pas pût être placée
    listZoneImage.removeLast();

    //dessin des images
    pixRes = new QPixmap(sizeResult);
    pixRes->fill();
    collageImage(listZoneImage, pixRes);

    return pixRes;
}

/**
 * placement des images avec l'epace entre les images automatique
 */
QPixmap* CollageWindow::pictureSpacingAuto()
{
    QPixmap     *pixRes;
    int         pictureSpacing;
    int         debut, fin, mil;

    //initialisation des paramètres de recherche
    debut = 25;
    fin = 200;
    mil = (debut + fin) / 2;

    //nombre de photos par défaut
    pictureSpacing = mil;

    //On modifie la taille du polygone de forme
    replacePolygon(params->getResultSize());
    while(resizePolygon(params->getResultSize()))
        replacePolygon(params->getResultSize());

    //remplissage de la liste des images
    QList<zoneImage*> listZoneImage = fillListZoneImage(this->params->getPictureQuantity(), this->params->getPictureSize());
    QList<zoneImage*> listZoneImageSave;

    while(debut < fin)
    {
        if(!PlacementListZoneImage(listZoneImage, params->getResultSize(), params->getPictureSize(), pictureSpacing))
        {
            if(fin != mil)
                fin = mil;
            else
                fin++;

            if( mil == (debut + fin) / 2)
                mil-=1;
            else
                mil = (debut + fin) / 2;

            pictureSpacing = mil;

            //reset de la position des images
            resetListZoneImage(listZoneImage);
        }
        else
        {
            if(debut != mil)
                debut = mil;
            else
                debut++;

            if( mil == (debut + fin) / 2)
                mil+=1;
            else
                 mil = (debut + fin) / 2;

            pictureSpacing = mil;

            //copie de la liste
            listZoneImageSave = copyListZoneImage(listZoneImage);

            //reset de la position des images
            resetListZoneImage(listZoneImage);
        }
    }

    listZoneImage = listZoneImageSave;

    //dessin des images
    pixRes = new QPixmap(params->getResultSize());
    pixRes->fill();
    collageImage(listZoneImage, pixRes);

    return pixRes;
}

/**
 * placement des images avec la taille des images automatique
 */
QPixmap* CollageWindow::pictureSizeAuto()
{
    QPixmap     *pixRes;
    QSize       sizeResult;
    int         sizePicture;
    int         debut, fin, mil;
    bool        trouve;

    //initialisation des paramètres de recherche
    debut = 1;
    fin = 2000;
    trouve = false;
    mil = (debut + fin) / 2;

    //taille de la feuille
    sizeResult = QSize(params->getResultWidth(),params->getResultHeight());

    //taille de départ
    sizePicture = mil;

    //On modifie la taille du polygone de forme en conséquence
    replacePolygon(sizeResult);
    while(resizePolygon(sizeResult))
        replacePolygon(sizeResult);

    //remplissage de la liste des images
    QList<zoneImage*> listZoneImage = fillListZoneImage(this->params->getPictureQuantity(), sizePicture);
    QList<zoneImage*> listZoneImageSave;

    while(debut < fin)
    {
        if(!PlacementListZoneImage(listZoneImage, sizeResult, sizePicture, params->getPictureDistance()))
        {
            if(fin != mil)
                fin = mil;
            else
                fin++;

            if( mil == (debut + fin) / 2)
                mil-=1;
            else
                 mil = (debut + fin) / 2;

            //On diminue le nombre d'images
            sizePicture = mil;

            //On remet a 0 la position des images
            resetListZoneImage(listZoneImage);

            //on resize les images
            foreach (zoneImage *zone, listZoneImage)
            {
                qDebug() << "avant: " << zone->image->width();
                resizePicture(zone->image,sizePicture);
                qDebug() << "après: " << zone->image->width();
            }
        }
        else
        {
            if(debut != mil)
                debut = mil;
            else
                debut++;

            if( mil == (debut + fin) / 2)
                mil+=1;
            else
                 mil = (debut + fin) / 2;

            //sauvegarde de la liste
            listZoneImageSave = copyListZoneImage(listZoneImage);

            //On diminue le nombre d'images
            sizePicture = mil;

            //On remet a 0 la position des images
            resetListZoneImage(listZoneImage);

            //on resize les images
            foreach (zoneImage *zone, listZoneImage)
            {
                resizePicture(zone->image,sizePicture);
            }
        }
    }

    //On récupère le dernier résultat valide
    listZoneImage = listZoneImageSave;

    //dessin des images
    pixRes = new QPixmap(sizeResult);
    pixRes->fill();
    collageImage(listZoneImage, pixRes);

    destroyListZoneImage(listZoneImage, true);

    return pixRes;
}

/**
 * placement des images avec la taille du résultat automatique
 */
QPixmap* CollageWindow::TailleResultAuto()
{
    QPixmap     *pixRes;
    int         size, sizeSave;
    QPolygon    polySave = *this->polygon;
    int         debut, fin, mil;
    bool        trouve;

    //initialisation des paramètres de recherche
    debut = 1;
    fin = 10000;
    trouve = false;
    mil = (debut + fin) / 2;

    //taille par défaut (la taille des photos * nombre de photos pour les 2 axes)
    size = mil;
    sizeSave = fin;

    //On modifie la taille du polygone de forme en conséquence
    replacePolygon(QSize(size,size));
    while(resizePolygon(QSize(size,size)))
        replacePolygon(QSize(size,size));

    //remplissage de la liste des images
    QList<zoneImage*> listZoneImage = fillListZoneImage(this->params->getPictureQuantity(), params->getPictureSize());
    QList<zoneImage*> listZoneImageSave;

    while(debut < fin)
    {
        if(!PlacementListZoneImage(listZoneImage, QSize(size, size), params->getPictureSize(), params->getPictureDistance()))
        {
            qDebug() << mil;
            if(debut != mil)
                debut = mil;
            else
                debut++;

            if( mil == (debut + fin) / 2)
                mil += 1;
            else
                 mil = (debut + fin) / 2;

            //réinitialisation de la position des images
            resetListZoneImage(listZoneImage);

            //On augmente homotétiquement la taille du résultat
            size = mil;

            //On modifie la taille du polygone de forme en conséquence
            replacePolygon(QSize(size,size));
            while(resizePolygon(QSize(size,size)))
                replacePolygon(QSize(size,size));
        }
        else
        {
            qDebug() << mil;
            if(fin != mil)
                fin = mil;
            else
                fin--;

            if( mil == (debut + fin) / 2)
                mil -= 1;
            else
                 mil = (debut + fin) / 2;

            //sauvegarde du résultat précédent
            if(size < sizeSave)
            {
                qDebug() << "save";
                destroyListZoneImage(listZoneImageSave, false);
                listZoneImageSave = copyListZoneImage(listZoneImage);
                sizeSave = size;
                polySave = *this->polygon;
            }

            //réinitialisation de la position des images
            resetListZoneImage(listZoneImage);
            size = mil;

            //On modifie la taille du polygone de forme en conséquence
            replacePolygon(QSize(size,size));
            while(resizePolygon(QSize(size,size)))
                replacePolygon(QSize(size,size));
        }

    }

    //On récupère le dernier résultat valide
    listZoneImage = listZoneImageSave;
    size = sizeSave;

    //on remet le polygone à la bonne taille
    *this->polygon = polySave;

    //dessin des images
    pixRes = new QPixmap(QSize(size,size));
    pixRes->fill();
    collageImage(listZoneImage, pixRes);

    //destruction de la liste
    destroyListZoneImage(listZoneImage, true);

    return pixRes;
}

/**
 *placement des zones d'image
 */
bool CollageWindow::PlacementListZoneImage(QList<zoneImage*> listZoneImage, QSize tailleResult, int sizePicture, int spacingPicture)
{
    QPoint* lastPos = new QPoint();

    int limiteRotation = (98*listZoneImage.count())/100;
    bool placee = false;

    //pour chaque zone d'image
    for(int i = 0; i<listZoneImage.count(); i++)
    {
        zoneImage *zone = listZoneImage.at(i);

        placee = PlacementZoneImage(listZoneImage, zone, tailleResult, sizePicture, spacingPicture, lastPos);

        //si l'image n'est pas placée mais que c'est l'une des dernières
        if(!placee && i >= limiteRotation)
        {
            int rotationOrg = zone->rotation;
            zone->rotation = (zone->rotation+10)%360;
            lastPos->setX(0);
            lastPos->setY(0);
            while(!PlacementZoneImage(listZoneImage, zone, tailleResult, sizePicture, spacingPicture, lastPos) && rotationOrg != zone->rotation)
            {
                zone->rotation = (zone->rotation+10)%360;
                lastPos->setX(0);
                lastPos->setY(0);
            }
            if(zone->posImage.x() == -1)
                return false;
        }
        else if(!placee)
            return false;
    }
    return true;
}

/**
 * Place l'image contenue dans zone par apport aux images déja placés dans la liste listZoneImage
 */
bool CollageWindow::PlacementZoneImage(QList<zoneImage*> listZoneImage, zoneImage* zone, QSize tailleResult, int sizePicture, int spacingPicture, QPoint* lastPos)
{
    QPoint newPos;

    //le pas est fixé a 2% du plus grand coté de la feuille
    int pasWidth = (2 * tailleResult.width()) / 100;
    int pasHeight = (2 * tailleResult.height()) / 100;

    //on ne s'occupe que des images qui ne sont pa encore placées
    if(zone->posImage.x() != -1)
    {
        return true;
    }

    //on commence la recherche a partir de la dernière position trouvée
    newPos = *lastPos;

    //balayage de la zone de travail
    for(int i = 0; i< tailleResult.height(); i += pasHeight)
    {
        for(int j = 0; j < tailleResult.width(); j += pasWidth)
        {
            //placement de l'image
            newPos.setX(j);
            newPos.setY(i);

            //test de la position de l'image
            if(RectInsidePolygoneForme(zone->image->rect(), newPos, zone->rotation)
                    && testEspacement(listZoneImage, newPos, zone->image->rect(), spacingPicture, sizePicture))
            {
                zone->posImage = newPos;
                *lastPos = newPos;
                return true;
            }
        }
    }

    return false;
}

/**
 * Convertisseur cm -> px
 */
int CollageWindow::convertCmToPixel(int cm)
{
    int screenMm  = QApplication::desktop()->widthMM();
    int screenPx  = QApplication::desktop()->width();

    return ((cm*screenPx)/screenMm);
}

/**
 *Vérifie l'espacement entre le centre de la nouvelle image et le centre des images
 *déja placés. true si pas de problème, false sinon
 */
bool CollageWindow::testEspacement(QList<zoneImage*> listZoneImage, QPoint newPos, QRect recImage, int espacementCible, int tailleImage)
{
    QLineF  line;
    qreal   espacement;
    int     espacementCiblePX;

    //conversion de l'espacement en pixel
    if(this->params->getFormatPictureSize() == Pixel || params->getAutoParam() == pictureSizeId)
        espacementCiblePX = (tailleImage * espacementCible) / 100;
    else
        espacementCiblePX = (convertCmToPixel(tailleImage) * espacementCible) / 100;

    //pour toutes les zones existantes
    foreach(zoneImage *zone, listZoneImage)
    {
        //on tient compte seulement des polygones déja placés
        if(zone->posImage.x() == -1)
            break;

        //on calcule la distance entre les 2 centres des 2 images
        line = QLineF(
                    QPointF(zone->posImage.x() + (zone->image->width()/2), zone->posImage.y() + (zone->image->height()/2)),
                    QPointF(newPos.x() + (recImage.width()/2), newPos.y() + recImage.height()/2));
        espacement = line.length();
        if(espacement<=espacementCiblePX)
            return false;
    }
    return true;
}
